//
// Created by fh on 2021/6/10.
//

#include "Sort.h"

void SortDsiplay(int a[],int length) {
    printf("打印数组: ");
    for (int i = 0; i < length; ++i) {
        printf("%d ",a[i]);
    }
    printf("\n");
}

/* 冒泡排序 */
void BubbleSort(int a[],int length) {
    /* 思考过程第1步:
     * 遍历整个数组，讲当前的元素跟下一个元素比较，哪个大就往后面挪，这样子只能遍历到最后一个元素的前一个元素，
     * 因为如果下标跑到最后一个元素的时候下一个元素就会越界了；遍历一次就会把数组里最大的数往后挪一个，一共有n
     * 个元素，所以用两重循环，一重是用来遍历一遍用的，一重是用来计算遍历次数用的，每挪动一个元素循环n-1次，
     * 共有n个元素需要挪动所以共遍历 ( n-1 ) * n 次，外层循环控制挪动多少个元素，内层循环用来遍历数组的下标
     * */
//    for (int i = 0; i < length; ++i) {
//        for (int j = 0; j < length-1; ++j) {
//            if (a[j] > a[j+1]) {
//                int temp = a[j+1];
//                a[j+1] = a[j];
//                a[j] = temp;
//            }
//        }
//    }

    /* 思考过程第2步:
     * 其实每次挪动一个元素到最后面的时候下一次遍历比较的时候已经挪动过的元素是不需要比较的，因为他已经是当前最大的了
     * 所以后面比较的时候已经挪到后面的元素是不需要遍历再比较的了，所以比较的次数是逐次递减的，具体说明：假设这里元素有11个
     * 第1次比较遍历从下标0跑到9，然后把最大的挪到了最后，第2次遍历的时候就只需要从下标0跑到8，然后就把第二大的挪到倒数第2
     * 个位置了，第3次遍历的时候又只需要此从下标0跑到7，然后就把第三大的挪到倒数第3个位置，以此类推...
     * */
//    for (int i = 0; i < length; ++i) {
//        for (int j = 0; j < length - i - 1; ++j) {
//            if (a[j] > a[j+1]) {
//                int temp = a[j+1];
//                a[j+1] = a[j];
//                a[j] = temp;
//            }
//        }
//    }

    /* 思考过程第3步: 优化
     * 其实当要挪动的元素只剩一个的时候已经是排好序了，因为只剩一个元素的时候就只有它了，不需要挪动了和比较了
     * 当遍历的下标是0、1那一刻之后后面的操作都可以不要了，因为比较完下标0和1之后需不需要交换搞完之后就是有序的了
     * 这样子可以少1次循环遍历
     * */
//    for (int i = 0; i < length; ++i) {
//        int k = length - i - 1;
//        if (k < 2) {
//            break;
//        }
//        for (int j = 0; j < k; ++j) {
//            if (a[j] > a[j+1]) {
//                int temp = a[j+1];
//                a[j+1] = a[j];
//                a[j] = temp;
//            }
//        }
//    }

    /* 思考过程第4步: 更优化，参考王铮数据结构与算法之美 :
     * "实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。"
     * */
    for (int i = 0; i < length; ++i) {
        // 提前退出冒泡循环的标志位
        int flag = 0;
        for (int j = 0; j < length - i - 1; ++j) {
            if (a[j] > a[j+1]) {
                int temp = a[j+1];
                a[j+1] = a[j];
                a[j] = temp;
                flag = 1; // 表示有数据交换
            }
        }
        // 没有数据交换，提前退出
        if (flag == 0) {
            break;
        }
    }

}

/* 插入排序:
 * 首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，
 * 就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的
 * 插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
 * 具体图解参考王铮的数据结构与算法之美 */
void InsertionSort(int a[],int length) {
    /* 外层循环是要插入的元素个数，因为从第二个元素开始后面的元素都要跟它前面的元素逐个比较判断一次
     * 内层循环是该元素前面的所有元素遍历，当发现前面的某个元素比它大的时候就把它往那个位置插进入，
     * 插进去之前需要把从这个比它大的元素的下标开始的元素到它的位置前一个的元素都往后移动一位，以便有空位插入
     * 这就是第二个循环里判断的作用。这个从前往后遍历判断的版本待优化 */
//    for (int i = 1; i < length; ++i) {
//        for (int j = 0; j < i; ++j) {
//            if (a[i] < a[j]) {
//                // 移动它前面的元素，从下标j开始
//                int t = a[i]; // 保存这个需要插入的元素的值，因为它前面的元素往后移的时候会把它覆盖掉
//                for (int k = i-1; k >= j; --k) {
//                    a[k+1] = a[k];
//                }
//                a[j] = t; // 将元素插入到发现比它大的那个位置
//            }
//        }
//    }

    /* 王铮版本代码: !!! 从后往前遍历比较和从前往后遍历比较的区别
     * 从后忘前面逐个比较判断可以少写一个循环的代码
     * 第二个循环是比较要插入的元素前面的元素，从后往前逐个判断，当发现当前位置里的元素比要插的元素大时
     * 就把它往后挪一个位置，如果发现当前元素比要插入的元素小那就跳出循环，此时j刚好是插入的位置的前一个位置，
     * 排到它后面，因为最开始比较的时候是从第二个元素开始的，所以这个时候能保证这个位置它前面的元素一定都是比要插入的元素小的了、
     * 这个代码的比较优化的是因为拿来插入的元素是从前往后拿的，所以前面那些操作过插入的元素都是有序的了，所以可以用break，不会
     * 出现这个跳出去比它小的元素前面的元素比它还大的
     * */

    /*
     * 插入排序的精髓就是先通过比较找到要插入的位置，再插入；比较过程则是在已插入的数据中进行比较。a[i]代表本次要插入的数，
     * a[j]代表已插入的数，j=i-1代表要比较的次数，第一次直接插入，第二次比较1个已插入数据，因为已插入数据都已经排好序，
     * 所以遇到小于自己的数直接跳出比较进行插入即可。左边是有序区，已经排好序了，比它小的前面不用再判断了，从前往后判断会多
     * 判断前面比要插入的元素小的元素，其实大可不必
     * */
    if (length <= 1) {
        return;
    }
    for (int i = 1; i < length; ++i) {
        int value = a[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
            if (a[j] > value) {
                // 从后往前移动所有比value大
                a[j+1] = a[j]; // 数据移动
            } else {
                // 不用比较到0下标的元素了，因为是从前面一个个决定要插入的，只要这时j的元素比value小，它前面的肯定不会比value大了
                break;
            }
        }
        // j 这个位置的元素是比value小或者等于value的元素位置下标
        a[j+1] = value; // 插入数据
    }

}

/* 选择排序
 * 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，
 * 将其放到已排序区间的末尾。详细图解见王铮数据结构与算法之美的图
 * */
void SelectionSort(int a[],int length) {
//    int b = 0;
//    length = 6;
//    for (int i = 0; i < length; ++i) {
//        for (int j = 0; j < length - i; ++j) {
//            printf("\ni = %d , j = %d",i,j);
//            printf("\n第%d次",++b);
//        }
//    }
//    printf("\n");

    for (int i = 0; i < length; ++i) {
        // 找出最小的元素
        int min = a[i];
        int index = i;
        // 这里j可以j=i+1，因为自己不需要跟自己比较
        for (int j = i; j < length; ++j) {
            if (min > a[j]) {
                min = a[j];
                index = j;
            }
        }
        // 交换
        int t = a[i];
        a[i] = min;
        a[index] = t;
    }

}

/* 递归测试 */
void recursionTest(int l,int r) {
    if (l >= r) {
        printf("back %d  %d\n",l,r);
        return;
    }
    int mid = (r+l)/2;
    printf("当前 l:%d  mid:%d  r:%d\n",l,mid,r);
    recursionTest(l,mid);
    recursionTest(mid+1,r);
    printf("操作 --------------------------------- %d  %d\n",l,r);
}

/* 合并 */
void merge(int array[],int l,int m,int r) {
    int curL = (r-l)+1;
    int *temp = (int *) malloc(sizeof(int) * curL);

    int i = l;
    int j = m + 1;
    int k = 0;
    for (; i <= m && j <= r;) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    if (i <= m) {
        for (int n = i; n <= m; ++n) {
            temp[k++] = array[n];
        }
    }
    if (j <= r) {
        for (int n = j; n <= r; ++n) {
            temp[k++] = array[n];
        }
    }

    for (int n = 0; n < curL; ++n) {
        printf("%d ",*(temp+n));
    }
    printf("\n");

    // 这个复制是关键,困扰了我很久,复制到原来的数组起始位置和结束位置都是传进来的左右下标
    // 进来的数组下标是排好序之后返回去的
    int t = 0;
    for (int n = l; n <= r; ++n) {
        array[n] = temp[t++];
    }
    free(temp);
    temp = NULL;

}
/* 拆分 */
void split(int array[],int l,int r) {
    if (l >= r) {
        return;
    }
    int mid = (l+r)/2;
    split(array,l,mid);
    split(array,mid+1,r);
    merge(array,l,mid,r);
}
/* 归并排序 */
void MergeSort(int a[],int length) {
    split(a,0,length-1);
}


/* 获取分区点：详细理解请看王铮排序下的图 */
int partition(int array[],int l,int r) {
    int value = array[r];
    /* i是一个游标，在他的左边的都是比value小的，在他的右边的都是比value大的，发现此时j下标的值比当前i的值大的话
     * 就不需要交换，当j下标的值比value小的话就需要把它移动到i的左边，那么此时交换i和j位置的值，然后i右移一位那么
     * 就能保证在i左边的是小于value的了，如果j比value大的话就不用交换，总之j指向的是一个个往后走的，当j跑到value
     * 的位置时跳出循环,之后将游标i所在的值跟这个value交换，跳出循环的时候不存在i位置的值比value小的，因为小的话i
     * 会往后面移动的
     * */
    int i = l;
    int j = l;
    while (j < r) {
        if (array[j] < value) {
            // 交换
            int t = array[j];
            array[j] = array[i];
            array[i] = t;
            i++;
        }
        j++;
    }
    // 到了最后一个分区点的时候交换一下
    int t = array[i];
    array[i] = array[j];
    array[j] = t;
    return i;
}

/* 快速排序拆分 */
void quickSplit(int array[],int l,int r) {
    if (l >= r) {
        return;
    }
    // q是分区点
    int q = partition(array,l,r);
    quickSplit(array,l,q-1);
    quickSplit(array,q+1,r);
}
/* 快速排序：
 * 快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
 * 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，
 * 数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r
 * 之间是大于 pivot 的。根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，
 * 直到区间缩小为 1，就说明所有的数据都有序了。*/
void QuickSort(int a[],int length) {
    quickSplit(a,0,length-1);
}


/* 计数排序:
 * 计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
 * 而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。*/
void CountingSort(int a[],int length) {
    // 先找出最大的,作为数组的最大下标
    int max = 0;
    for (int i = 0; i < length; ++i) {
        if (max < a[i]) {
            max = a[i];
        }
    }
//    printf("最大值:%d\n",max);

    int createL = max+1;
    int *c = (int *) malloc(createL * sizeof(int));
    // 需要初始化为0
    for (int i = 0; i < createL; ++i) {
        c[i] = 0;
    }
    // test init value
//    SortDsiplay(c,createL);

    for (int i = 0; i < length; ++i) {
        int value = a[i];
        (*(c+value))++;
//      同 *(c+value) = ++*(c+value); // 同 *(c+value) = ++(*(c+value));
    }
//    SortDsiplay(c,createL);

    int totle = 0;
    for (int i = 0; i < createL; ++i) {
        totle += c[i];
        c[i] = totle;
    }
//    SortDsiplay(c,createL);

    // 存储排序后的临时数组
    int *r = (int *) malloc(length * sizeof(int));
    for (int i = length-1; i >= 0; --i) {
        int value = a[i];
        int t = c[value];
        r[t-1] = value;
        c[value] = t-1;
    }
//    SortDsiplay(r,length);
    // 将排序后的数组复制到原来的数组
    for (int i = 0; i < length; ++i) {
        a[i] = r[i];
    }

    free(c);
    c = NULL;
    free(r);
    r = NULL;
}

/* 二分查找:
 * 二分查找要警惕终止条件、区间上下界更新方法、返回值选择 */
int DichotomySearch(int a[],int length,int value) {
    /*
//   自己实现的算法
    int mid = (length-1)/2;
    while (mid != 0 && mid != length-1) {
        if (value < a[mid]) {
            mid = (0+(mid-1))/2;
        } else if (value > a[mid]) {
            mid = ((mid+1)+(length-1))/2;
        } else {
            return mid;
        }
    }
    if (mid == 0) {
        if (value == a[mid]) {
            return 0;
        }
    }
    if (mid == length-1) {
        if (value == a[mid]) {
            return length-1;
        }
    }
    return -1;

    //*/
    /* 建议看王铮代码比较短 */
    /* 王铮代码版本 */
    int low = 0;
    int high = length-1;
    while (low <= high) {
        int mid = (low + high) / 2; // mid = low + ((high - low) >> 1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}



/* 求一个正浮点数的平方根 */
double pingfanggen(double value) {
    if (value <= 0) {
        return -1;
    }
    double left = 0;
    double right = value;
    double mid = (left + right) / 2.0;
    double current = mid * mid;
    /* 保留三位小数 */
    while (fabs(value - current) > 0.001) {
        if (current < value) {
            left = mid;
            mid = (left + right) / 2;
        } else if (current > value) {
            right = mid;
            mid = (left + right) / 2;
        } else {
            return mid;
        }
        current = mid * mid;
    }
    return mid;
}

/* 二分查找变体：
 * 变体一：查找第一个值等于给定值的元素 */
int DichotomySearchOne(int a[],int length,int value) {
    int low = 0 ;
    int high = length-1;
    while (low <= high) {
        int mid = low + ((high - low)>>1);
        if (value < a[mid]) {
            // 在左边
            high = mid - 1;
        } else if (value > a[mid]) {
            // 在右边
            low = mid + 1;
        } else {
            if (mid == 0 || a[mid-1] != value) {
                // 如果已经是第一个元素(它前面没有了，他自己就是第一个找到的值了)或者它前面的那个值不是相同的值(说明它就是第一个了)
                // 因为是短路判断,mid == 0 写在前面比较好,因为如果先判断a[mid-1] != value万一mid等于零0就会数组越界判断了
                return mid;
            } else {
                // 继续往左找
                high = mid - 1;
            }
            // return mid; 如果是原味(找到就返回)直接返回
        }
    }
    return -1;
}
/* 二分查找变体：
 * 变体二：查找最后一个值等于给定值的元素 */
int DichotomySearchTwo(int a[],int length,int value) {
    int low = 0;
    int high = length-1;
    while (low <= high) {
        int mid = low + ((high - low)>>1);
        if (value < a[mid]) {
            high = mid - 1;
        } else if (value > a[mid]) {
            low = mid + 1;
        } else {
            if (mid == length-1 || a[mid+1] != value) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}
/* 二分查找变体：
 * 变体三：查找第一个大于等于给定值的元素 */
int DichotomySearchThree(int a[],int length,int value) {
    int low = 0;
    int high = length-1;
    while (low <= high) {
        int mid = low + ((high - low)>>1);
        if (a[mid] >= value) {
            if (mid == 0 || a[mid-1] < value) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return -1;
}
/* 二分查找变体：
 * 变体四：查找最后一个小于等于给定值的元素 */
int DichotomySearchFour(int a[],int length,int value) {
    int low = 0;
    int high = length-1;
    while (low <= high) {
        int mid = low + ((high-low) >> 1);
        if (a[mid] <= value) {
            if (mid == length - 1 || a[mid+1] > value) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
}

/* 排序测试demo */
void SortTestDemo() {


    {
        printf("--------------------------- 冒泡排序 ------------------------\n");
        int a[] = {2,25,1,7,3,8,4,12,9,5,10};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
        BubbleSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);
    }

    {
        printf("--------------------------- 插入排序 ------------------------\n");
        int a[] = {2,6,1,7,3,8,4,11,9,5,10};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
        InsertionSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);
    }

    {
        printf("--------------------------- 选择排序 ------------------------\n");
//        int a[] = {4,5,6,3,2,1};
        int a[] = {2,6,1,7,3,8,4,11,9,5,10};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
        SelectionSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);
    }

    {
//        recursionTest(0,12);
        printf("--------------------------- 归并排序 ------------------------\n");
        int a[] = {2,25,1,7,3,8,4,12,9,5,10};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
        MergeSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);
    }
    {
        printf("--------------------------- 快速排序 ------------------------\n");
//        int a[] = {6,11,3,9,8};
//        int a[] = {6,1,3,2,8};
        int a[] = {6,8,3,2,8};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
//        partition(a,0,length-1);
        QuickSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);

    }
    {
        printf("--------------------------- 计数排序 ------------------------\n");
        int a[] = {2,6,25,1,7,3,8,4,12,9,5,10};
//        int a[] = {2,5,3,0,2,3,0,3};
//        int a[] = {8,4,16,2,10,12,14,6};
        int length = sizeof(a) / sizeof(int);
        printf("排序前\n");
        SortDsiplay(a,length);
        CountingSort(a,length);
        printf("排序后\n");
        SortDsiplay(a,length);
    }
    {
        printf("--------------------------- 二分查找 ------------------------\n");
        int a[] = {0,1,3,4,5,8};
        int length = sizeof(a) / sizeof(int);
        int result = DichotomySearch(a,length,4);
        printf("%d\n",result);
    }
    {
        printf("--------------------------- 求平方根 ------------------------\n");
        double result = pingfanggen(5);
        printf("%f\n",result);
    }

}
